#include<iostream>

using namespace std;

bool hashPathCore(const char * matrix , int rows, int cols, int row, int col, const char* ch, 
    bool * visited , int& strLength){
    // 已经将字符数组遍历完毕
    if ( ch[strLength] == '\0' ){
        return true;
    }

    bool hashPath = false;

    if ( row >=0 && row < rows && col >= 0 && col < cols && matrix[row*cols+col] == ch[strLength] && !visited[row*cols+col]){

        strLength ++;
        
        visited[row*cols+col] = true;

        hashPath = hashPathCore(matrix, rows, cols, row-1, col, ch, visited, strLength) 
            || hashPathCore(matrix, rows, cols, row, col+1, ch, visited, strLength) 
            || hashPathCore(matrix, rows, cols, row+1, col, ch, visited,strLength) 
            || hashPathCore(matrix, rows, cols, row, col-1, ch, visited,strLength); 
        
        // 回退到上一步
        if ( !hashPath ){
            strLength --;
            visited[row*cols+col] = false;
        }
    }

    return hashPath;
}

bool hashPath(const char * matrix, int rows, int cols, const char * ch){
    if ( matrix==nullptr || rows < 1 || cols < 1 || ch == nullptr)
        return false;
    bool * visited = new bool[rows*cols];

    int strLength = 0;
    for ( int row = 0; row < rows ; row ++ ){
        for ( int col = 0; col < cols; col ++ ){
            if ( hashPathCore(matrix, rows, cols, row, col, ch, visited, strLength) ){
                return true;
            }
        }
    }

    delete[] visited;
    return false;
}


int main(void){
    const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";
    const char* str = "SLHECCEIDEJFGGFIE";
    //const char* matrix = "abtgcfcsjdeh";
    //const char* str = "bfce";
    cout << hashPath(matrix, 3,4,str) << endl;
    return 0;
}